﻿#include <iostream>

using namespace std;

static int* getNextArray(const char* subStr)
{
    size_t strSize = strlen(subStr);
    int* nextArr = (int*)malloc(strSize * sizeof(int));
    memset(nextArr, 0, strSize * sizeof(int));
    nextArr[0] = -1;
    nextArr[1] = 0;
    int index = 2;
    int cn = 0;
    while (index < strSize)
    {
        if (subStr[index - 1] == subStr[cn])
        {
            nextArr[index++] = ++cn;
        }
        else if (cn > 0)
        {
            cn = nextArr[cn];
        }
        else
        {
            nextArr[index++] = 0;
        }
    }

    return nextArr;
}

static int indexOf(const char* str, const char* subStr)
{
    if (!str || !subStr) return -1;

    size_t subStrSize = strlen(subStr);
    if (subStrSize == 0) return 0;

    size_t strSize = strlen(str);
    if (strSize == 0) return -1;

    if (subStrSize == 1)
    {
        for (int i = 0; i < strSize; i++)
        {
            if (str[i] == subStr[0]) return i;
        }

        return -1;
    }

    if (strSize == subStrSize)
    {
        if (strcmp(str, subStr) == 0) return 0;
        return -1;
    }

    int* nextArr = getNextArray(subStr);
    int index1 = 0;
    int index2 = 0;
    while (index1 < strSize && index2 < subStrSize)
    {
        if (str[index1] == subStr[index2])
        {
            ++index1;
            ++index2;
        }
        else if (nextArr[index2] >= 0)
        {
            index2 = nextArr[index2];
        }
        else
        {
            ++index1;
        }
    }

    free(nextArr); 
    return index2 >= subStrSize ? index1 - index2 : -1;
}

/**
 * KMP算法解决的问题
 * 字符串str1和str2, str1是否包含str2, 如果包含则返回str2在str1中开始的位置。
 * 如何做到时间复杂度O(N)完成?
 *
 * 针对子串，声明一个数组，用于存放某一个位置i的字符之前的有重复子串的字符个数, 且这个重复子串的最后一个字符是位置i-1(最长前缀 最长后缀), 比如
 *
 *           a   b   c   d   f   c   a   b   c   d   f   g
 * next[]:  -1   0   0   0   0   0   0   1   2   3   4   5
 *
 * next[0] = -1, next[1] = 0, 前两项人为规定。
 * 从next[2]开始，需要看之前是否有出现过2次的子字符串。
 * 这个例子，next[2] - next[6]都是0.
 * 从第7位置'b'开始，前面有 "a b c d f c a", 前后都有一个'a', 后一个'a'在6位置，故next[7] = 1
 * 第8位置'c', 前面有"a b c d f c a b", 前后缀是: "ab"，最后的字符'b'在7位置，next[8] = 2
 * 第9位置'd', 前面有"a b c d f c a b c", 前后缀是: "abc"。故next[9] = 3
 * ......
 *
 * 有了针对子串做的这个next数组，则可以用于加速在目标字符串中查找这个子串出现的索引。
 * 设目标字符串是一个很长的串：
 *
 * ... a  b  c  a  b  e  p  a  b  c  a  b  e  ?  ...
 *                                           ↑
 *                                          位置i
 *
 * 要查找的子串是:
 *
 * 子串：    a  b  c  a  b  e  p  a  b  c  a  b  e  g
 * next[]: -1  0  0  0  1  2  0  0  1  2  3  4  5  6
 *
 * 如果i位置是'g'，则找到了这个字符串，索引是 i - subString.length + 1;
 * 如果i位置不是'g'，则找到子串next数组的'g'位置的数值，将子串的指针指向这个数值的索引位置，
 * 子串：    a  b  c  a  b  e  p  a  b  c  a  b  e  g
 * next[]: -1  0  0  0  1  2  0  0  1  2  3  4  5  6
 *                           ↑
 *
 * 假设目标串i的位置是'p', 则可以基于子串前缀"abcabe"继续向后匹配，加速了原来的查找流程。
 *
 * 当然，如果不是'p', 因为子串指针位置的next数组的值是0，则只能从目标串的i位置重新开始匹配子串的第一个字符了。
 *
 * 假想，如果next的这个位置不是0，则可以将指针继续前移到next刚才的值的位置，继续与源字符串向后匹配.
 * 举例：
 * ... a  b  a  b  e  a  b  a  b  ?  ...
 *
 * 子串：    a  b  a  b  e  a  b  a  b  g
 * next[]: -1  0  0  1  2  0  1  2  3  4
 *
 * ?不是'g'，则：
 *
 * 子串：    a  b  a  b  e  a  b  a  b  g
 * next[]: -1  0  0  1  2  0  1  2  3  4
 *                     ↑
 *
 * ?也不是'e'，则:
 *
 * 子串：    a  b  a  b  e  a  b  a  b  g
 * next[]: -1  0  0  1  2  0  1  2  3  4
 *               ↑
 *
 * ?如果是'a', 则接着匹配?后面的字符；如果不是'a', 则从?开始，以子串的第一个字符重新开始匹配。
 */
int main_StringIndexOf()
{
    char subStr[256] = "uijk";
    char str[256] = "abcdfcabcdfuijkgabcdfcabcdfg";
    int index = indexOf(str, subStr);
    printf("%d\n", index);
    return 0;
}